import sun.awt.windows.ThemeReader;
import sun.reflect.generics.tree.Tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-03-12
 * Time: 23:21
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
//     BFS
//     每层遍历到第一个元素就修改值
//     DFS
//     每次遍历到一个新的高度就修改结果
    public int findBottomLeftValue(TreeNode root) {
        int ans=0;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode temp=queue.poll();
            // 如果这样写的话
            // 必须先右再左, 这样最左边的节点才是最后遍历到的
            // 当然也可以通过记录每层的节点个数, 每次只到遍历到第一个节点时再修改ans
            if(temp.right!=null){
                queue.add(temp.right);
            }
            if(temp.left!=null){
                queue.add(temp.left);
            }
            ans=temp.val;
        }
        return ans;
    }
}
